#include <vector>
// 矩阵搜索
using namespace std;
bool searchMatrix(vector<vector<int>> &matrix, int target) {
  int rows = matrix.size();
  int cols = matrix[0].size();
  if (rows == 0 || cols == 0) {
    return false;
  }
  for (int col = 0; col < cols; col++) {
    // 列搜索
    int left = 0;
    int right = rows - 1;
    while (left <= right) {
      int mid = (left + right) / 2;
      int midValue = matrix[mid][col];
      if (target == midValue) {
        return true;
      } else if (target < midValue) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
  }
  return false;
}
// 解法二
bool searchMatrix_(vector<vector<int>> &matrix, int target) {
  int rows = matrix.size();
  int cols = matrix[0].size();
  if (rows == 0 || cols == 0) {
    return false;
  }
  int right = cols - 1;
  int up = 0;
  while (right >= 0 && up < rows) {
    if (target == matrix[right][up]) {
      return true;
    } else if (target < matrix[right][up]) {
      right--;
    } else {
      up++;
    }
  }
  return false;
}
int main() {
  vector<vector<int>> m{{{5}, {6}}};
  bool isOk = searchMatrix(m, 6);
  return 0;
}